package com.salim.leetcode.$60;

import java.util.ArrayList;
import java.util.List;

public class PermutationSequence {
    public String getPermutation(int n, int k) {
        if(n==1){
            return "1";
        }
        List<Integer> number = new ArrayList<>();
        StringBuilder sb = new StringBuilder();
        int total = 1;
        for(int i=1;i<=n;i++){
            total*=i;
            number.add(i);
        }
        for(int i=n;i>2;i--){
            int sector = (k-1)/(total/i);
            sb.append(
                number.remove(sector)
            );
            k = k-sector*(total/i);
            total = total/i;
        }
        if(k ==1){
            sb.append(
                number.remove(0)
            );
            sb.append(
                number.remove(0)
            );
        }else{
            sb.append(
                number.remove(1)
            );
            sb.append(
                number.remove(0)
            );
        }
        return sb.toString();
    }
    public static void main(String[] args) {
        PermutationSequence p = new PermutationSequence();
        //i.insert(new int[][]{{1, 3},{6,9}},new int[]{2,5});
        p.getPermutation(3,2);
//        p.getPermutation(4,6);
    }
}
